package riofrio;

import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Map;
import java.util.Stack;
import riofrio.TreeNode;

/**
 *
 * @author Victor Hugo Herrera Maldonado
 */
class PostOrderDepthFirstWalkIterator<T> implements Iterator<TreeNode<T>> {
    private final Stack<TreeNode<T>> stack=new Stack<>();
    private final Map<TreeNode<T>, Object> already=new IdentityHashMap<>();

    PostOrderDepthFirstWalkIterator(TreeNode<T> root) {
        stack.push(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public TreeNode<T> next() {
        TreeNode<T> nextNodeInStack = stack.peek();
        if(nextNodeInStack.isParent()) {
            TreeNode<T> node = nextNodeInStack;
            while(node != null && !already.containsKey(node)){
                ListIterator<TreeNode<T>> reverseIterator = node.reverseIterator();
                TreeNode<T> child=null;
                while(reverseIterator.hasNext()) {
                    child = reverseIterator.next();
                    stack.push(child);
                }
                already.put(node, true);
                node=child;
            }
        }
        return stack.pop();
    }
    
}
